import java.util.Arrays;
import java.util.Stack;

public class test {
    //插入排序方法一:时间复杂度为O(n^2);空间复杂度为O(1)；稳定
    public static void paixu1(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            for ( int j=i-1;j>=0;j--){
                if(arr[j]>temp){//直接插入到arr[j]位置
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
                else {
                    break;
                }
            }
        }
    }
    // 插入排序方法二:时间复杂度为O(n^2);空间复杂度为O(1)；稳定
    public static void paixu2(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];//找到temp的正确位置
                }
                else {
                    break;
                }
            }
            arr[j+1]=temp;//找到后再插入
        }
    }
    //希尔排序；时间复杂度为O(n~n^2);空间复杂度为O(1);不稳定
    public static void haset(int arr[]) {
        int gap = arr.length;
        while (gap >1) {
            gap /= 2;
            hpa(arr,gap);
        }
    }
    private  static void hpa(int arr[],int gap){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }
    //选择排序:时间复杂度为O(n^2);空间复杂度为O(1);不稳定
    public static void xtion1(int arr[]){
        for (int i=0;i< arr.length;i++){
            int temp=i;
            for (int j=i+1;j< arr.length;j++){
                if(arr[j]<arr[temp]) {
                    temp= j;
                }
            }
            if(arr[temp]<arr[i]){
                swap(arr,i,temp);
            }
        }
    }
    public static void xtion2(int arr[]){
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int minindex= left;
            int maxindex=left;//用maxindex=right就需要去套两个for循环增加运行时间
            for(int i=left+1;i<=right;i++){
                if(arr[i]<arr[minindex]){
                    minindex=i;
                }
                if(arr[i]>arr[maxindex]){
                    maxindex=i;
                }
            }
            swap(arr,left,minindex);
            //第一个数是最大值
            if(left==maxindex){
                maxindex=minindex;
            }
            swap(arr,right,maxindex);
            left++;
            right--;
        }
    }
    //堆排序:时间复杂度为O(n*logn)；空间复杂度为O(1);不稳定
    public static void duipa(int []arr){
        int end= arr.length-1;
        while (end>0){
            dadui(arr,end);
            swap(arr,0,end);
            end--;
        }
    }
    private static void dadui(int []arr,int end){
        int usize= end;
        for (int parten=(usize-1)/2;parten>=0;parten--){
            int childer=parten*2+1;
            while(childer<=usize){
                if(childer+1<usize&&arr[childer]<arr[childer+1]){
                    childer++;
                }
                if(arr[parten]<arr[childer]){
                    swap(arr,parten,childer);
                    parten=childer;
                    childer=parten*2+1;
                }
                else{
                    break;
                }
            }
        }
    }
    //冒泡排序
    public static void mppx(int []arr){
        for (int i = 0; i <arr.length ; i++) {
            boolean flag=false;
            for (int j = 0; j< arr.length-1-i; j++) {//一次次确定最小值
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
        if(!flag){
            break;
        }
        }
    }
    public static void quikpai(int[]arr){
        quik(arr,0, arr.length-1);
    }
    public static void quikpai1(int[]arr){
        quik1(arr,0, arr.length-1);
    }
   private static void quik(int[]arr,int start,int end){
        if(start>=end){
            return;
        }
        swap(arr,start,cent(arr,start,end));
        int cent=quike(arr,start,end);
        quik(arr,start,cent-1);
        quik(arr,cent+1,end);
    }
    private static void quik1(int[]arr,int start,int end){//不使用递归去快排
        swap(arr,start,cent(arr,start,end));
        int cent=quike(arr,start,end);
        Stack<Integer> stack=new Stack<>();
        if(cent>start+1){
            stack.push(start);
            stack.push(cent-1);
        }
        if(cent<end-1){
            stack.push(cent+1);
            stack.push(end);
        }
        end=stack.pop();
        start=stack.pop();
        cent=quike(arr,start,end);
        while (!stack.isEmpty()){
            if(cent>start+1){
                stack.push(start);
                stack.push(cent-1);
            }
            if(cent<end-1){
                stack.push(cent+1);
                stack.push(end);
            }
            end=stack.pop();
            start=stack.pop();
            cent=quike(arr,start,end);
        }
    }
    private static int quike(int []arr,int start,int end){
        int cent=start;
        while(start<end){
            while (start<end&&arr[end]>=arr[cent]){//注意先从end向后找
                end--;
            }
            while (start<end&&arr[start]<=arr[cent]){
                start++;
            }
            swap(arr,start,end);
        }
        swap(arr,cent,start);
        return start;
    }
    private  static  int cent(int []arr,int start,int end){//找中位数的下标
        int mid=(start+end)/2;
        if(arr[start]<arr[end]){
            if(arr[mid]<arr[start]){
               return start;
            }
            if(arr[mid]>arr[end]){
                return end;
            }
            else{
                return mid;
            }
        }
        else {
            if(arr[mid]>arr[start]){
                return start;
            }
            if(arr[mid]<arr[end]){
                return end;
            }
            else{
                return mid;
            }
        }
    }

    public static void wquikpai(int []arr){
        wquik(arr,0, arr.length-1);
    }
    private static void wquik(int[]arr,int start,int end){
        if(start>=end){
            return;
        }
        int cent=wquike(arr,start,end);
        wquik(arr,start,cent-1);
        wquik(arr,cent+1,end);
    }
    private  static int wquike(int []arr,int start,int end){
        int cent=start;
        int paiv=arr[start];
        while(start<end){
            while (start<end&&arr[end]>=paiv){
              end--;
            }
            arr[start]=arr[end];
            while (start<end&&arr[start]<=arr[cent]){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=paiv;
        return start;
    }
    public static void shuang(int []arr){
        wshuang(arr,0,arr.length-1);
    }
    private static void wshuang(int []arr,int start,int end){
        if(start>end){
            return;
        }
        int ret=wshuange(arr,start,end);
        wshuang(arr,0,ret-1);
        wshuang(arr,ret+1,end);
    }
    private static int wshuange(int[]arr,int start,int end){
        int pavi=start;
        int cur=start+1;
        while (cur<=end){
            if(arr[cur]<arr[start]&&arr[++pavi]!=arr[cur]){
                swap(arr,pavi,cur);
            }
            cur++;
        }
        //pavi停的位置就是arr[start]的位置；
        swap(arr,pavi,start);
        return pavi;
    }
    // 归并排序
    public static void  merg(int []arr){
        mergsort(arr,0,arr.length-1);
    }
    private static void mergsort(int []arr,int start,int end){
        if(start==end){
            return;
        }
        int mid=(start+end)/2;
        mergsort(arr,start,mid);
        mergsort(arr,mid+1,end);
        merghebin(arr,start,end,mid);
    }
    public static void merg1(int[]arr){
        mergsort1(arr,0,arr.length-1);
    }
    public static void mergsort1(int[]arr,int start,int end){//采用非递归的方式
        int gap=1;
        while (gap<arr.length) {
            for (int i = 0; i < arr.length; i += 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid>=arr.length){
                    mid=arr.length-1;
                }
                if(right>=arr.length){
                    right=arr.length-1;
                }
                merghebin(arr, left,right,mid);
            }
            gap *= 2;
        }
    }
    private static void merghebin(int []arr,int start,int end,int mid){
        int se=start;
        int sl=mid;
        int te=mid+1;
        int tl=end;
        int []temparr=new int[end-start+1];
        int k=0;//表示temparr的下标
        while (se<=sl&&te<=tl){
            if(arr[se]<=arr[te]){
                temparr[k++]=arr[se++];
            }
            else {
                temparr[k++]=arr[te++];
            }
        }
        while (se<=sl){
            temparr[k++]=arr[se++];
        }
        while (te<=tl){
            temparr[k++]=arr[te++];
        }
        for(int i=0;i<end-start+1;i++){
            arr[i+start]=temparr[i];
        }
    }
    private static void swap(int []arr,int ret1,int ret2){
        int temp=arr[ret1];
        arr[ret1]=arr[ret2];
        arr[ret2]=temp;
    }

    public static void main(String[] args) {
        int []arr1={5,6,4,2,7,9,1,2};
        paixu1(arr1);
        System.out.println("插叙1排序"+Arrays.toString(arr1));
        int []arr2={64,45,15,51,1,5,31};
        paixu2(arr2);
        System.out.println("插叙2排序"+Arrays.toString(arr2));
        int []arr3={64,112,56,46,95};
        haset(arr3);
        System.out.println("希尔排序"+Arrays.toString(arr3));
        int []arr4={64,45,15,51,1,5,31,88,46,95};
        xtion1(arr4);
        System.out.println("选择排序1"+Arrays.toString(arr4));
        int []arr5={10,6,4,2,7,9,1,2};
        xtion2(arr5);
        System.out.println("选择排序2"+Arrays.toString(arr5));
        int []arr6={8,6,91,3,56,1,656,2};
        duipa(arr6);
        System.out.println("堆排序"+Arrays.toString(arr6));
        int []arr7={2,1,3,7,5};
        mppx(arr7);
        System.out.println("冒泡排序"+Arrays.toString(arr7));
        int []arr8={8,6,4,2,7,9,1,2};
        quikpai(arr8);
        System.out.println("Hoare快速排序"+Arrays.toString(arr8));
        int []arr9={4,5,8,1,2,9,11,15,88};
        wquikpai(arr9);
        System.out.println("挖坑法快速排序"+Arrays.toString(arr9));
        int []arr10={4,5,8,1,2,9,11,88,18};
        shuang(arr10);
        System.out.println("前后指针法快排"+Arrays.toString(arr10));
        int []arr11={4,5,8,1,2,9,11,88,18};
        quikpai1(arr11);
        System.out.println("非递归快排"+Arrays.toString(arr11));
        int []arr12={45,65,45,89,97,111,12,1,2,5,6};
        merg(arr12);
        System.out.println("递归法归并排序"+Arrays.toString(arr12));
        int []arr13={45,65,45,89,97,111,12,1,2,5,6};
        merg1(arr13);
        System.out.println("非递归归并排序"+Arrays.toString(arr13));
    }
}

